/*
Problem Description
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。
Input
本题目包含多组测试，请处理到文件结束。
在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。
当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。
当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。
Output
对于每一次询问操作，在一行里面输出最高成绩。
Sample Input
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
5
6
5
9
 */
package com.yuan.algorithms.team20150724;

import java.io.BufferedInputStream;
import java.util.Scanner;

/**
 * @author YouYuan
 * @eMail E-mail:1265161633@qq.com
 * @Time 创建时间：2015年8月4日 下午2:45:11
 * @Explain 说明:学习利用数组存储线段树
 */
public class 线段树_区间查询最大分数_学习数组实现 {

	static int[] max = new int[200000 << 2];
//	static int[] score = new int[200005];
//	static int i;
	static Scanner in = new Scanner(new BufferedInputStream(System.in));
//	static Scanner in = new Scanner(System.in);

	public static void main(String[] args) {
		while (in.hasNext()) {
			int n = in.nextInt();
			int m = in.nextInt();
//			for (int i = 1; i <= n; i++) {
//				score[i] = in.nextInt();
//			}
//			i = 1;
			buildTree(1, n, 1);
			while (--m >= 0) {
				char c = in.next().charAt(0);
				int a = in.nextInt();
				int b = in.nextInt();
				if (c == 'Q') {
					System.out.println(query(a, b, 1, n, 1));
				} else {
					update(a, b, 1, n, 1);
				}
			}
		}
	}

	/**
	 * 根据学生编号和新值更新线段树数据
	 * 
	 * @param number
	 *            学生编号
	 * @param newValue
	 *            新值
	 * @param left
	 * @param right
	 * @param index
	 */
	private static void update(int number, int newValue, int left, int right, int index) {
		if (left == right) {
			max[index] = newValue;
			return;
		}
		int mid = (left + right) >> 1;
		if (number <= mid) {
			update(number, newValue, left, mid, index << 1);
		} else {
			update(number, newValue, mid + 1, right, index << 1 | 1);
		}
		max[index] = Math.max(max[index << 1], max[index << 1 | 1]);
	}

	/**
	 * 查询区间[a,b]的最大分数
	 * 
	 * @param a
	 * @param b
	 * @param left
	 * @param right
	 * @param index
	 */
	private static int query(int a, int b, int left, int right, int index) {
		/****这里的判断条件很关键*****/
		
		/****此种写法超内存*****/
//		if (a<left && b > right) {
//			return max[index];
//		}
//		if (a == left && b == right) {
//			return max[index];
//		}
		
		/****此种写法可AC*****/
		if (a <= left && right <= b) {//判断查询区间是否包含当前区间，是的话返回当前区间的最大分数
			return max[index];
		}
		int mid = (left + right) >> 1;
		int max = 0;
		if (a <= mid) {// 判断查询的区间是否在左子树
			max = query(a, b, left, mid, index << 1);
		}
		if (b > mid) {// 判断查询的区间是否在右子树
			max = Math.max(max, query(a, b, mid + 1, right, index << 1 | 1));// 综合左子树和右子树的查询情况获得最大值
		}
		return max;
	}

	/**
	 * 构建线段树
	 * 
	 * @param left
	 *            左区间下标
	 * @param right
	 *            右区间下标
	 * @param index
	 *            线段树下标
	 */
	private static void buildTree(int left, int right, int index) {
		if (left == right) {
//			max[index] = score[i++];
			max[index] = in.nextInt();
			return;
		}
		int mid = (left + right) >> 1;
		buildTree(left, mid, index << 1);
		buildTree(mid + 1, right, index << 1 | 1);
		max[index] = Math.max(max[index << 1], max[index << 1 | 1]);
	}

}
